package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;
import cn.pugle.oj.catalog.MathProblem;

/**
 * 数学解法
 *
 * @author tzp
 * @since 2020/9/15
 */
public class LC62 implements DynamicProblem, MathProblem {
    public int uniquePaths(int m, int n) {
        int a = Math.max(m, n);
        int b = Math.min(m, n);
        if (b == 1) return 1;
        long up = factorial(a + b - 1 - 1, a);
        long result = up / factorial(b - 1, 1);
        return (int) (result);
    }

    public static long factorial(long big, long small) {
        if (big == small)
            return small;
        else
            return big * factorial(big - 1, small);
    }

    public static void main(String[] args) {
//        System.out.println(factorial(2,1));
//        System.out.println(factorial(3,1));
//        System.out.println(factorial(5,3));
//        System.out.println(new LC62().uniquePaths(4, 2));
//        System.out.println(new LC62().uniquePaths(7, 3));
//        System.out.println(new LC62().uniquePaths(8, 3));
        System.out.println(new LC62().uniquePaths(2, 1));
    }
}
